package BasicDataStructures;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

/**
 *假设需要实现一个api：randomKey() ，从哈希表中随机获取一个key
 * 使用数组实现随机取元素很方便
 * 因此我们将所有元素都存在arr（一个集合中），这样子随机取数比较方便
 * 再维护一个map，记录key->index的键值对，方便我们从arr中读取元素。酱紫我们get（）操作复杂度还是o（1）
 * @param <K>
 * @param <V>
 */
public class MyArrayHashMap<K,V> {

    private static class Node<K,V> {
        K key;
        V value;

        Node(K key , V value){
            this.key = key;
            this.value = value;
        }
    }

    //存储key在arr中的索引
    private final HashMap<K,Integer> map = new HashMap<>();

    //真正存储key-value键值对的数组
    private final ArrayList<Node<K,V>> arr = new ArrayList<>();

    private final Random r = new Random();

    public V get(K key) {
        //map中不存在这个key
        if (!map.containsKey(key)) {
            return null;
        }
        //map中存在这个key
        //从map中取出key对应的下标，便于从arr中取出
        int index = map.get(key);
        Node<K,V> node = arr.get(index);
        return node.value;
    }

    public void put(K key,V value) {
        //若arr中已经存在这个key，则修改arr中这个key对应的value值
        if (map.containsKey(key)){
            int index = map.get(key);
            Node<K,V> node = arr.get(index);
            node.value = value;
            return;
        }

        arr.add(new Node<>(key, value));
        map.put(key,arr.size()-1);
    }

    public void remove(K key) {

        if (!map.containsKey(key)){
            return;
        }

        //找出待删除的元素
        int index = map.get(key);
        Node<K,V> node = arr.get(index);
        //找出arr中最后一个元素
        Node<K,V> e = arr.get(arr.size()-1);

        //交换index上的元素和最后一个元素
        arr.set(index,e);
        arr.set(arr.size()-1,node );

        //最后一个元素被换了位置，需要修改他的索引
        map.put(e.key,index);

        arr.remove(arr.size()-1);

        map.remove(node.key);

    }

    //随机弹出一个key
    public K randomKey(){
        int n = arr.size();
        int randomIndex = r.nextInt(n);
        return arr.get(randomIndex).key;
    }

    public boolean containsKey(K key) {
        return map.containsKey(key);
    }

    public int size() {
        return map.size();
    }

    public static void main(String[] args) {
        MyArrayHashMap<Integer, Integer> map = new MyArrayHashMap<>();
        map.put(1, 1);
        map.put(2, 2);
        map.put(3, 3);
        map.put(4, 4);
        map.put(5, 5);

        System.out.println(map.get(1)); // 1
        System.out.println(map.randomKey());

        map.remove(4);
        System.out.println(map.randomKey());
        System.out.println(map.randomKey());
    }
}
